package com.wtgroup.demo.leetcode.q221_最大正方形;

/**
 * @author 60906
 * @date 2021/5/10 19:11
 */
public class Q221 {


    class Solution {
        public int maximalSquare(char[][] matrix) {
            // 最大边长
            int maxLen = 0;
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return maxLen;
            }

            int rowCnt = matrix.length;
            int colCnt = matrix[0].length;

            int[][] dp = new int[rowCnt][colCnt];


            for (int i = 0; i < rowCnt; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if(matrix[i][j] == '0') continue;
                    // 第一行 or 第一列
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                    }
                    maxLen = Math.max(dp[i][j], maxLen);
                }
            }

            return maxLen * maxLen;
        }
    }

}
